package TDACP;
import java.util.Comparator;

public class Heap<K extends Comparable<K>,V> implements PriorityQueue<K,V>{
	
	protected Entrada<K,V> [] elems;
	protected Comparator<K> comp;
	protected int size;
	
	public Heap(int maxElem, Comparator<K> c){
		elems = (Entrada<K,V> []) new Entrada[maxElem];
		comp = c;
		size = 0;
	}
	
	public Heap(int maxElem){
		elems = (Entrada<K,V> []) new Entrada[maxElem+1];
		comp = new DefaultComparator<K>();
		size = 0;
	}
	
	
	public int size(){
		return size;
	}
	
	public boolean isEmpty(){
		return size==0;
	}
	
	public Entry<K,V> max() throws EmptyPriorityQueueException{
		if (isEmpty())
			throw new EmptyPriorityQueueException("Cola con prioridad vacia"); 
		return elems[1];
	}
	
	public Entry<K,V> insert(K key, V value) throws InvalidKeyException{
		if (key==null)
			throw new InvalidKeyException("Key nulo");
		Entrada<K,V> entrada = new Entrada<K,V>(key,value);
		elems[++size] = entrada;
		
		int i = size;
		boolean seguir = true;
		while(i>1 && seguir){
			Entrada<K,V> elemActual = elems[i];
			Entrada<K,V> elemPadre = elems[i/2];
			if(comp.compare(elemActual.getKey(),elemPadre.getKey()) > 0){
				Entrada<K,V> aux = elems[i];
				elems[i] = elems[i/2];
				elems[i/2] = aux;
				i/=2;
			}
			else
				seguir = false;				
		}
		return entrada;
	}
	
	public Entrada<K,V> removeMax()throws EmptyPriorityQueueException{
		if (isEmpty())
			throw new EmptyPriorityQueueException ("Cola con prioridad vacia");
		Entrada<K,V> toReturn = elems[1];
		if(size==1){
			size = 0;
			elems[1] = null;
		}
		else{
			elems[1] = elems[size];
			elems[size] = null;
			size--;
			
			int i = 1;
			boolean seguir = true;
			while(seguir){
				int hi = 2*i;
				int hd = 2*i+1;
				boolean tieneHijoIzquierdo = hi <= size();
				boolean tieneHijoDerecho = hd <= size();
				if(!tieneHijoIzquierdo)
					seguir = false;
				else{
					int m;
					if(tieneHijoDerecho){
						if(comp.compare(elems[hi].getKey(), elems[hd].getKey()) > 0)
							m = hi;
						else
							m = hd;
					}
					else
						m = hi;
					if (comp.compare(elems[i].getKey(), elems[m].getKey()) < 0){
						Entrada<K,V> aux = elems[i];
						elems[i] = elems[m];
						elems[m] = aux;
						i = m;
					}
					else
						seguir = false;
				}
			}
		}
		return toReturn;
	}
}
